The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology.
Packet switching systems, like most systems, include many subsystems which must work in a coordinated fashion for the overall system to operate. In fact, certain functions may require a common timing reference or at least some level of synchronization to operate properly, and some functions may be able to take advantage of the synchronization to operate more efficiently. Depending on the size and capacity of a particular switching system, components of the switching system may be distributed across several components, boards, subsystems, cabinets, rooms, or even remotely located. In many of these configurations, a common timing strobe is infeasible. Desired are improved methods and systems for synchronizing components of communications and computer systems.
Moreover, consumers and designers of these packet switching systems typically desire high reliability and increased performance at a reasonable price. Commonly used techniques for helping to achieve these goals are for these systems to perform some level of flow control to avoid certain congestion conditions, and to provide multiple paths between a source and a destination.
In packet switching systems which provide multiple paths between a source and a destination, packets of information are typically distributed among, and routed over these multiple paths. It is typically more cost-effective to provide multiple slower rate links or switching paths, than to provide a single higher rate path. Such designs also achieve other desired performance characteristics. However, a typical artifact of routing across multiple links of varying delays is the need to resequence each of the streams of packets routed through a packet switch back into their original order.
One known technique for routing and resequencing streams of packets is to add a sequence number to each packet and then to place packets in sequential order based on these added sequence numbers. Separate sequence numbers are typically used for each switch input-output pairing. For example, each input interface of the packet switch maintains a separate sequence number counter for each output of the packet switch; and each output interface of the packet switch maintains a separate counter for each input of the packet switch. This technique is simple, but it requires significant resources for the buffers and sequence number counters. The resources required for these buffers and counters must be sufficient to store the packets and distinguish the order of the packets for handling worst case delay differentials between paths. This problem is further compounded when contiguous sequence numbers are not used or when a packet is lost or dropped. In either of these cases, it is hard to determine whether certain packets should be forwarded immediately or should be delayed to see if a potentially dropped or lost packet or a packet with the skipped sequence number actually arrives. Desired are improved methods and systems for routing and resequencing packets in a packet switch, especially those methods and systems which place a bound on the size requirements of sequence numbers or other resources.
Packet switching systems typically monitor and maintain certain fundamental characteristics and information concerning their operation, such as packet counts and buffer occupancies of queues and other elements in distributed locations in a packet switching system. These characteristics, either natively or after manipulation, (herein also referred to as, and included in the extensible term “flow control information”), can be used to identify potential congestion and other traffic and switch conditions, which may then be used to make flow control decisions and generate reactive signals or messages to decrease or eliminate the potential or actual problem conditions.
However, before such flow control decisions may be made, the underlying information must be communicated to a location which can make decisions to generate the flow control messages. These flow control messages then need to be sent to the locations that react to the flow control decisions. For example, traffic between a source and destination may be routed across multiple paths through a packet switching system, and traffic going to a particular destination may be sent from multiple sources. Also, in typical packet switching systems, packets may be queued at various locations such as in various stages of a switching fabric. Thus, the flow control information concerning the traffic going to a destination or even between a source destination pair may be distributed throughout the packet switching system, and typically is not native at the location or to the process which makes the flow control signaling decisions. One mechanism for distributing control information is to broadcast the information in reaction to the detection of a predefined condition. This approach typically generates a large peak of messages at a time when the switching system is possibly already suffering from a lack of bandwidth in one or more locations within itself. Another possible mechanism for communicating the flow control information to the requisite flow control decision points and for communicating the decisions to the reaction points is for each element having flow control information to autonomously and periodically broadcast such information. However, this autonomous approach can lead to congestion and delays. Desired are improved methods and systems for distributing flow control and other information in a packet switching system.